
#include "residues.h" 
#include "backtracking.h"
#include <iostream>

using namespace std;

/*********************
 * class of Residues * 
 *********************/

/*
inline
bool Residues::isValid(int b)
{ 
  return csp->isValid(varj, b)
}
*/

/************************
 * class of FIFO_simple * 
 ************************/

void FIFO_simple::initialize(int k, int i1, int j1, int a1)
{

  // cout << "FIFO_simple::initialization" << endl;
  set(k, i1, j1, a1); 
  try {
    cache = new int [k];
  }
  catch(bad_alloc){
    cerr << "Memory exhausted." << endl;
  }
  tail = -1;
  // cout << "  Done of initialization." << endl;
}

bool FIFO_simple::findSupport()
{
  int p;
  for (p = 0; p <= tail; p++){
    if(csp->isValid(varj, cache[p])) {
      csp->addDchecks(p+1);
      return true;
    }
  }
  csp->addDchecks(p);
  return false; 
}


void FIFO_simple::initAdd(int b)
{
  tail = 0;
  cache[0] = b;
  // cout << "FIFO_simple::initAdd" << endl;
}

void FIFO_simple::add(int b)
{
  if(tail < cacheSize-1)
    tail++; 
  for (int current = tail; current > 0; current--){
    cache[current] = cache[current-1];
  }
  csp->addOchecks(tail);
  cache[0] = b;
}

/**********************
 * class of FIFO_full * 
 **********************/

void FIFO_full::initialize(int k, int i1, int j1, int a1) 
{
  set(k, i1, j1, a1); 
  tail = -1;
  current = -1;
  try{
    cache = new int [k];
  }
  catch(bad_alloc){
    cerr  << "Memory exhausted." << endl;
  }
};

/* findSupport: find if there is a support in cache.
 * current will be made to point to the support if 
 * there is one. In this way, all non-valid supports 
 * will be automatically at the end of the circular array (0..tail)
 * in an decending ordering of recentness of non-validity.
 */
bool FIFO_full::findSupport()
{
  int stop = current - 1, p = current;
  bool found = false;

  // search from current to tail
  for(; p <= tail; p++)
    if (csp->isValid(varj, cache[p])){
      csp->addDchecks(p-current+1);
      found = true;
      break;
    }
  if (!found) {
    csp->addDchecks(p-current); 
    // search from head to current-1
    for(p = 0; p <= stop; p++)
      if (csp->isValid(varj, cache[p])){
	csp->addDchecks(p+1);
	found = true;
	break;
      }
    if (!found)
      csp->addDchecks(p); 
  }
  if (found){
    current = p; 
  }
  return found;
}

void FIFO_full::initAdd(int b)
{
  tail = 0;
  current = 0;
  cache[current] = b;
  // cout << "FIFO.initAdd" << endl;
}

void FIFO_full::add(int b)
{
  if (tail < cacheSize - 1){
    tail++; 

    // move supports after current one step forward
    for(int p = tail; p > current; p--){
      cache[p] = cache[p-1];
    }
    csp->addOchecks(tail-current); 
    cache[current] = b;
  }
  else if (current == 0) {
    current = tail;
    cache[tail] = b;
  }
  else { 
    // add b to the current position 
    cache[current-1] = b; 
    current--;
  }
}

/************************
 * class of FIFO_update * 
 ************************/

void FIFO_update::initialize(int k, int i1, int j1, int a1)
{
  set(k, i1, j1, a1);
  
  try{
    cache = new int [k];
  }
  catch(bad_alloc){
    cerr  << "Memory exhausted." << endl;
  }
}

void FIFO_update::initAdd(int b)
{
  tail = 0; 
  cache[0] = b;
}

bool FIFO_update::findSupport()
{
  bool found = false;
  int support; 
  int p; 

  for(p = 0; p <= tail; p++){
    if (csp->isValid(varj, cache[p])) {
      csp->addDchecks(p+1); 
      found = true; 
      break;
    }
  }

  if (found) {
    support = cache[p]; 
    // move the current support to the head 
    for(int i = p; i > 0; i--){
      cache[i] = cache[i-1];
    }
    csp->addOchecks(p); 
    cache[0] = support; 
  }
  else csp->addDchecks(p); 

  return found;
}

void FIFO_update::add(int b)
{
  if (tail < cacheSize-1)
    tail++; 
  for(int i = tail; i > 0; i--){
    cache[i] = cache[i-1];
  }
  csp->addOchecks(tail); 
  cache[0] = b;
}

/***************************
 * class of Fitness_simple * 
 ***************************/

void Fitness_simple::initialize(int k, int i1, int j1, int a1)
{
  set(k, i1, j1, a1);

  try{
    cache = new Node [k];
  }
  catch(bad_alloc){
    cerr  << "Memory exhausted." << endl;
  }
}

bool Fitness_simple::findSupport()
{
  int i;

  for(i=0; i <= tail; i++)
    if(csp->isValid(varj, cache[i].r)){
      csp->addDchecks(i+1);
      return true;
    }
  csp->addDchecks(i); // not found
  return false;
};

void Fitness_simple::insInc(int r, int fitness)
{
  int insPos;

  for(insPos = 0; insPos <= tail; insPos++){
    if(fitness <= cache[insPos].fitness)
      break;
  }

  if (tail < cacheSize-1)
    tail++;
  else if(insPos > tail) // no replacement occurs
    return ;

  for(int i = tail; i > insPos; i--){
    cache[i] = cache[i-1];
  }
  csp->addOchecks(tail-insPos);
  cache[insPos].r = r;
  cache[insPos].fitness = fitness;
}

void Fitness_simple::insDec(int r, int fitness)
{
  int insPos;

  /* find where to insert, when these is a tie, 
   * the recentness is used to break the tie. 
   */
  for(insPos = 0; insPos <= tail; insPos++)
    if (fitness >= cache[insPos].fitness)
      break;

  if (tail < cacheSize-1){ // insPos: correct position to insert r
    tail++;
  }
  else if(insPos > tail) // when level is the shallowest, no replacement
    return;
  
  for(int i = tail; i > insPos; i--){
    cache[i] = cache[i-1];
  }
  csp->addOchecks(tail-insPos);

  cache[insPos].r = r;
  cache[insPos].fitness = fitness;
}


/****************************
 * class of MINLEVEL_simple * 
 ****************************/

void MINLEVEL_simple::add(int b){
  insDec(b, csp->getPhase());
};

void MINLEVEL_simple::initAdd(int b) 
{
  tail = 0;
  cache[0].r = b;
  cache[0].fitness = csp->getPhase();
}


/****************************
 * class of MAXLEVEL_simple * 
 ****************************/

void MAXLEVEL_simple::add(int b)
{
  insInc(b, csp->getPhase());
}

void MAXLEVEL_simple::initAdd(int b) 
{
  tail = 0;
  cache[0].r = b;
  cache[0].fitness = csp->getPhase();
}

/*****************************
 * class of MAXDOMAIN_simple * 
 *****************************/

void MAXDOMAIN_simple::add(int b)
{
  insInc(b, csp->getDomSize(varj));
}

void  MAXDOMAIN_simple::initAdd(int b) 
{
  tail = 0;
  cache[0].r = b;
  cache[0].fitness = csp->getDomSize(varj);
}

/*****************************
 * class of MINDOMAIN_simple * 
 *****************************/

void MINDOMAIN_simple::add(int b)
{
  insDec(b, csp->getDomSize(varj));
}

void MINDOMAIN_simple::initAdd(int b)
{
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = csp->getDomSize(varj);
}

/***************************
 * class of Fitness_update * 
 ***************************/

bool Fitness_update::findSupport(int& i) 
{
  for(i=0; i <= tail; i++){
    if(csp->isValid(varj, cache[i].r)){
      csp->addDchecks(i+1); 
      return true;
    }
  }
  csp->addDchecks(i); 
  return false;
};

void Fitness_update::updateInc(int i1, int fitness)
{
  int j1;
  Node p;

  if(fitness == cache[i1].fitness)
    return ;

  // move cache[i1] to the proper place by using its new fitness

  p.r = cache[i1].r;
  p.fitness = fitness;
  if(fitness < cache[i1].fitness){
    for (j1 = i1; j1 > 0; j1--){
      if(fitness >= cache[j1-1].fitness)
	break;
      else
	cache[j1] = cache[j1-1];
    }
    csp->addOchecks(i1-j1); 
    cache[j1] = p;
  }
  else {
    for (j1 = i1; j1 < tail; j1++){
      if(fitness <= cache[j1+1].fitness)
	break;
      else
	cache[j1] = cache[j1+1];
    }
    csp->addOchecks(j1-i1);
    cache[j1] = p;
  }
}

void Fitness_update::updateDec(int i1, int fitness)
{
  int j1;
  Node p;

  if(fitness == cache[i1].fitness)
    return ;

  // move cache[i1] to the proper place by using its new fitness

  p.r = cache[i1].r;
  p.fitness = fitness;

  if(fitness < cache[i1].fitness){
    for (j1 = i1; j1 < tail; j1++){
      if(fitness >= cache[j1+1].fitness)
	break;
      else
	cache[j1] = cache[j1+1];
    }
    csp->addOchecks(j1-i1);
    cache[j1] = p;
  }
  else {
    for (j1 = i1; j1 > 0; j1--){
      if(fitness <= cache[j1-1].fitness)
	break;
      else
	cache[j1] = cache[j1-1];
    }

    csp->addOchecks(i1-j1);
    cache[j1] = p;
  }
}

/*****************************
 * class of  MINLEVEL_update * 
 *****************************/

bool MINLEVEL_update::findSupport()
{
  bool found;
  int pos; 
  
  // double check the call of the parent class members
  found = Fitness_update::findSupport(pos);
    
  if (found)
    updateDec(pos, csp->getPhase());
  return found;
}

void MINLEVEL_update::add(int b)
{
  insDec(b, csp->getPhase());
}

void MINLEVEL_update::initAdd(int b){
  tail = 0;
  cache[0].r = b;
  cache[0].fitness = csp->getPhase();
}

/*****************************
 * class of  MAXLEVEL_update * 
 *****************************/

void MAXLEVEL_update::add(int b) 
{
    insInc(b, csp->getPhase());
}

void MAXLEVEL_update::initAdd(int b)
{
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = csp->getPhase();
}

bool MAXLEVEL_update::findSupport()
{
    bool found;
    int pos; 
  
    // double check the call of the parent class members
    found = Fitness_update::findSupport(pos);
    
    if (found)
      updateInc(pos, csp->getPhase());
    return found;
}

/*****************************
 * class of MINDOMAIN_update * 
 *****************************/

void  MINDOMAIN_update::add(int b)
{
    insDec(b, csp->getDomSize(varj));
}

void MINDOMAIN_update::initAdd(int b)
{
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = csp->getDomSize(varj);
}

bool MINDOMAIN_update::findSupport()
{
    bool found;
    int pos; 
    
    // double check the call of the parent class members
    found = Fitness_update::findSupport(pos);
    
    if (found)
      updateDec(pos, csp->getDomSize(varj));
    return found;
}

/*****************************
 * class of MAXDOMAIN_update * 
 *****************************/

void MAXDOMAIN_update::add(int b)
{
    insInc(b, csp->getDomSize(varj));
}

void MAXDOMAIN_update::initAdd(int b) 
{
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = csp->getDomSize(varj);
}

bool MAXDOMAIN_update::findSupport() 
{
    bool found;
    int pos; 
    
    // double check the call of the parent class members
    found = Fitness_update::findSupport(pos);
    
    if (found)
      updateInc(pos, csp->getDomSize(varj));
    return found;
}

/***************************
 * class of  MAXUSE_update * 
 ***************************/

bool MAXUSE_update::findSupport()
{
  // find the support and its frequency
  int pos;
  bool found;

  found = Fitness_update::findSupport(pos);

  if (found)
    updateInc(pos, cache[pos].fitness+1);
  
  return found;
}

/***************************
 * class of  MINUSE_update * 
 ***************************/

bool MINUSE_update::findSupport()
{
  int pos;
  bool found;

  found = Fitness_update::findSupport(pos);
  
  if (found)
    updateDec(pos, cache[pos].fitness+1);
  
  return found;
}

/*************************
 * class of  MINUSE_full * 
 *************************/

bool MINUSE_full::findSupport()
{
  int pos, curFitness=0, curR=0;
  int pos1, pos2;
  bool found = false;

  // find if there is a current support in cache
  for(pos = 0; pos <= tail; pos++){
    if(csp->isValid(varj, cache[pos].r)){
      found = true;
      curR = cache[pos].r;
      curFitness = cache[pos].fitness + 1;
      csp->addDchecks(pos+1);
      break;
    }
    else cache[pos].fitness--;
  }

  // if not found, do nothing else
  if (!found) {
    csp->addDchecks(pos); 
    return false;
  }

  // otherwise, sort the updated cache
  // 1. move <curR, curFitness> at pos to the correct position
  // 2. move the ones from 0 to pos to the correct positions

  // 1. pos1: the position for <curR, curFitness>
  for(pos1 = pos; pos1 > 0; pos1--){
    if(curFitness <= cache[pos1-1].fitness)
      break;
    else
      cache[pos1] = cache[pos1-1];
  }

  csp->addOchecks(pos-pos1);

  cache[pos1].r = curR;
  cache[pos1].fitness = curFitness;
  
  // 2. adjust the suppports from pos1+1 to pos
  //    by finding the supports with the same 
  //    fitness as cache[pos].fitness
  if(pos1 < pos) {
    curFitness = cache[pos].fitness;
    for(pos2 = pos; pos2 >= 0; pos2--){
      if (curFitness != cache[pos2].fitness)
	break;
    }
    pos2++;
    
    for(int i = pos2; i <= pos; i++)
      temp[i] = cache[i];

    // pos1: the insert position for curFitness
    for(pos1 = pos+1; pos1 <= tail; pos1++){
      if(curFitness >= cache[pos1].fitness)
	break;
    }
    pos1--;

    // move cach[pos+1 ... pos1] to positions starting from pos2
    for(int i = pos+1; i <= pos1; i++){
      cache[pos2 + i-pos-1] = cache[i];
    }
    csp->addOchecks(pos1-pos); 

    // move the stuff in temp to pos+1...pos1
    for(int i=pos; i >= pos2; i--){
      cache[pos1+i-pos] = temp[i];
    }
    csp->addOchecks(pos2-pos+1);
  }
  return found;
}

/*************************
 * class of  MAXUSE_full * 
 *************************/

bool MAXUSE_full::findSupport()
{
  int pos, curFitness=0, curR=0;
  int pos1;
  bool found = false;

  // find if there is a current support in cache
  for(pos = 0; pos <= tail; pos++){
    if(csp->isValid(varj, cache[pos].r)){
      found = true;
      curR = cache[pos].r;
      curFitness = cache[pos].fitness + 1;
      csp->addDchecks(pos+1);
      break;
    }
    else cache[pos].fitness--;
  }

  // if not found, do nothing else
  if (!found) {
    csp->addDchecks(pos); 
    return false;
  }

  // otherwise, sort the updated cache
  //   i.e., move <curR, curFitness> at pos to the correct position

  for(pos1 = pos; pos1 < tail; pos1++){
    if(curFitness <= cache[pos1+1].fitness)
      break;
    else
      cache[pos1] = cache[pos1+1];
  }
  csp->addOchecks(pos1-pos);

  cache[pos1].r = curR;
  cache[pos1].fitness = curFitness;
  
  return found;
}
